{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Negative Numbers in a Sorted Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countNegatives"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计有序矩阵中的负数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m&nbsp;* n</code>&nbsp;的矩阵&nbsp;<code>grid</code>，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。&nbsp;请你统计并返回&nbsp;<code>grid</code>&nbsp;中 <strong>负数</strong> 的数目。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]\n",
    "<strong>输出：</strong>8\n",
    "<strong>解释：</strong>矩阵中共有 8 个负数。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[3,2],[1,0]]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 100</code></li>\n",
    "\t<li><code>-100 &lt;= grid[i][j] &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计一个时间复杂度为 <code>O(n + m)</code> 的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-negative-numbers-in-a-sorted-matrix](https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-negative-numbers-in-a-sorted-matrix](https://leetcode.cn/problems/count-negative-numbers-in-a-sorted-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]', '[[3,2],[1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        for r in range(m):\n",
    "            for c in range(n):\n",
    "                if grid[r][c] < 0:\n",
    "                    ans += n - c\n",
    "                    break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        sum=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j]<0:\n",
    "                    sum+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        l,r = 0,n \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            while l<r:\n",
    "                mid = (l+r)>>1\n",
    "                if grid[i][mid]<0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid+1\n",
    "            # print(i,l,r)\n",
    "            res+=(n-l)\n",
    "            r,l = l,0\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for item in grid:\n",
    "            for i in item:\n",
    "                if i < 0 :\n",
    "                    res += 1\n",
    "        return res\n",
    "# 暴力穷举法"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        s1 = str(grid)\n",
    "        return s1.count('-')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        # 每行二分\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        num = 0\n",
    "        for i in range(m):\n",
    "            row = grid[i]\n",
    "            left = 0\n",
    "            right = n - 1\n",
    "            # 我们需要找到从右往左数第一个负数的索引\n",
    "            # m - 1 - 该索引 就是这个这一行中负数的个数\n",
    "            locate = n\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                val = row[mid]\n",
    "                if val >= 0:\n",
    "                    left = mid +1 \n",
    "                else:\n",
    "                    # val < 0\n",
    "                    locate = mid\n",
    "                    right = mid - 1\n",
    "            \n",
    "            \n",
    "            num += (n - locate)\n",
    "            \n",
    "\n",
    "        return num\n",
    "\n",
    "                \n",
    "\n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        x, y = M-1, 0\n",
    "        while x>=0 and y<N:\n",
    "            if grid[x][y] >= 0:\n",
    "                y += 1\n",
    "            else:\n",
    "                ans += N - y\n",
    "                x -= 1\n",
    "        return ans\n",
    "\n",
    "#  4,  3,  2, -1\n",
    "#  3,  2,  1, -1\n",
    "#  1,  1, -1, -2\n",
    "# -1, -1, -2, -3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        i,j = n-1, 0\n",
    "        ans = 0\n",
    "        while i > -1:\n",
    "            while grid[i][j] >= 0:\n",
    "                j += 1\n",
    "                if j == m:\n",
    "                    return ans\n",
    "            ans += m - j\n",
    "            i -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] < 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for nums in grid:\n",
    "            l = 0\n",
    "            r = len(nums) - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if nums[mid] < 0:\n",
    "                    r = mid\n",
    "                else:\n",
    "                    l = mid + 1\n",
    "            if nums[l] < 0:\n",
    "                res += len(nums) - l\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        i = 0 ;  j = len(grid[0]) - 1\n",
    "        \n",
    "\n",
    "        while i < len(grid) and j >= 0 :\n",
    "            if grid[i][j] >= 0 :\n",
    "                i += 1\n",
    "            else:\n",
    "                ans += len(grid) - i \n",
    "                j -= 1\n",
    "\n",
    "\n",
    "        return ans  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#  [ 4,  3,  2,  -1]\n",
    "#  [ 3,  2,  1,  -1]\n",
    "#  [ 1,  1, -1,  -2]\n",
    "#  [-1, -1, -2,  -3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        r=len(grid)#行\n",
    "        c=len(grid[0])#从0开始的列\n",
    "        i,j=r-1,0\n",
    "        ans=0\n",
    "        while i>=0 and j<=c-1:\n",
    "            if grid[i][j]<0:\n",
    "                ans+=(len(grid[0])-j)\n",
    "                i-=1\n",
    "            elif grid[i][j]>=0:\n",
    "                j+=1 #to right\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        a = 0\n",
    "        for item in grid:\n",
    "            for num in item:\n",
    "                if num < 0:\n",
    "                    a += 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        i,j=m-1,0\n",
    "        ans=0\n",
    "        while i>=0:\n",
    "            while j<n:\n",
    "                if grid[i][j]<0:\n",
    "                    ans=ans+n-j\n",
    "                    i-=1\n",
    "                    break\n",
    "                else:\n",
    "                    j=j+1\n",
    "            if j==n:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n=len(grid[0])\n",
    "        count=0        \n",
    "        for i in range(len(grid)):\n",
    "            j=0\n",
    "            while j<n:\n",
    "                if grid[i][j]<0:\n",
    "                    count=count+len(grid[i][j:])\n",
    "                    break\n",
    "                else:\n",
    "                    j+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        num=0\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]<0:\n",
    "                    num+=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for num in grid:\n",
    "            num.reverse()\n",
    "            count += bisect_left(num , 0)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        copy_grid = grid.copy()\n",
    "        for i in copy_grid:\n",
    "            i.sort()\n",
    "            for j in i:\n",
    "                if j >= 0:\n",
    "                    break\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        def counts(x):\n",
    "            count = 0\n",
    "            for i in range(len(x)-1,-1,-1):\n",
    "                if x[i]>=0:\n",
    "                    break\n",
    "                else:\n",
    "                    count = count+1\n",
    "            return count\n",
    "        res = 0\n",
    "        for i in grid:\n",
    "            res = res+counts(i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            grid[i].sort()\n",
    "            result += bisect_left(grid[i], 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        s = 0\n",
    "        las = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m-1,-1,-1):\n",
    "            l,r = las,n-1\n",
    "            ans = -1\n",
    "            while l<=r:\n",
    "                mid = (l+r)>>1\n",
    "                if grid[i][mid]>=0:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    ans = mid\n",
    "                    r = mid-1\n",
    "            if ans==-1:\n",
    "                break\n",
    "            s += n-ans\n",
    "            las = ans\n",
    "            # print(s,ans)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        s = 0\n",
    "        las = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        for i in range(m-1,-1,-1):\n",
    "            l,r = las,n-1\n",
    "            ans = -1\n",
    "            while l<=r:\n",
    "                mid = (l+r)>>1\n",
    "                if grid[i][mid]>=0:\n",
    "                    l = mid+1\n",
    "                else:\n",
    "                    ans = mid\n",
    "                    r = mid-1\n",
    "            if ans==-1:\n",
    "                break\n",
    "            s += n-ans\n",
    "            las = ans\n",
    "            # print(s,ans)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for li in grid:\n",
    "            if li[0]<0:\n",
    "                count = count + len(li)\n",
    "            elif li[len(li)-1]>0:\n",
    "                pass\n",
    "            else:\n",
    "                for i in li:\n",
    "                    if i < 0:\n",
    "                        count +=1\n",
    "                    else:\n",
    "                        continue\n",
    "                \n",
    "\n",
    "        return count \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        pos = col\n",
    "        num = 0\n",
    "        for i in range(row):\n",
    "            for j in range(pos):\n",
    "                if grid[i][j] < 0:\n",
    "                    num += col-j\n",
    "                    pos = j+1\n",
    "                    break\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            if grid[i][-1] >= 0:\n",
    "                continue\n",
    "            left, right = 0, len(grid[i])\n",
    "            while left < right:\n",
    "                mid = (left + right) >> 1\n",
    "                if grid[i][mid] >= 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            ans += len(grid[i]) - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for r in grid:\n",
    "            for c in range(len(r)):\n",
    "                if r[c]<0:\n",
    "                    res += len(r)-c\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] < 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        copy_grid = grid.copy()\n",
    "        for i in copy_grid:\n",
    "            i.sort()\n",
    "            for j in i:\n",
    "                if j >= 0:\n",
    "                    break\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        num,i,j = 0,0,len(grid[0])-1\n",
    "        while i < n and j >= 0:\n",
    "            if grid[i][j] < 0:\n",
    "                num += n - i\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        ans = 0\n",
    "        x, y = M-1, 0\n",
    "        while x>=0 and y<N:\n",
    "            if grid[x][y] >= 0:\n",
    "                y += 1\n",
    "            else:\n",
    "                ans += N - y\n",
    "                x -= 1\n",
    "        return ans\n",
    "\n",
    "#  4,  3,  2, -1\n",
    "#  3,  2,  1, -1\n",
    "#  1,  1, -1, -2\n",
    "# -1, -1, -2, -3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        def check(m):\n",
    "            return m<0\n",
    "        for i in grid:\n",
    "            ans += len(grid[0])- bisect_left(i, True, key=check)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        if grid[-1][-1] >= 0:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in grid:\n",
    "            if i[-1] >= 0:\n",
    "                continue\n",
    "            left,right = 0, len(grid[0])-1\n",
    "            while left <= right:\n",
    "                mid = (left+right)//2\n",
    "                if i[mid] >= 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            ans += len(grid[0]) - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        sum=0\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                if j<0:\n",
    "                    sum+=1\n",
    "        return sum            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "            res=0\n",
    "            for nums in grid:\n",
    "                left,right=0,len(nums) -1\n",
    "                while left<=right:\n",
    "                    mid=(left+right)//2\n",
    "                    if nums[mid]>=0:\n",
    "                        left=mid+1    #找到第一个负数所在的下标\n",
    "                    elif nums[mid] < 0:\n",
    "                        right=mid-1\n",
    "                res+=len(nums)-left\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                cnt += 1 if j < 0 else 0\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for r in grid:\n",
    "            for x in r:\n",
    "                if x < 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        for i in range(0, len(grid)):\n",
    "            for j in range(0, len(grid[0])):\n",
    "                if grid[i][j] < 0:\n",
    "                    cnt += len(grid[0]) - j\n",
    "                    break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        s = 0\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        las = n-1\n",
    "        for i in range(m):\n",
    "            while las>-1 and grid[i][las]<0:\n",
    "                las-=1\n",
    "            if las==-1:\n",
    "                s+=(m-i)*n\n",
    "                break\n",
    "            \n",
    "            s+=(n-las-1)\n",
    "        return s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        count=0        \n",
    "        for i in range(m):\n",
    "            j=0\n",
    "            while j<n:\n",
    "                if grid[i][j]<0:\n",
    "                    count=count+len(grid[i][j:])\n",
    "                    break\n",
    "                else:\n",
    "                    j+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#二分法\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        ans = 0\n",
    "        for i in grid:  #i为依次取每一个小[]，例如i=1时grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]中取[4,3,2,-1]\n",
    "            left,right=0,len(i)-1\n",
    "            while left<right:\n",
    "                mid = left+(right-left)//2\n",
    "                if i[mid]>=0:\n",
    "                    left = mid+1\n",
    "                else:\n",
    "                    right = mid\n",
    "            #以上为找到第一个为负数的值，每一个[]中最大的负数\n",
    "            if i[left]<0:\n",
    "                    ans+=len(i)-left\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] < 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for i in range(0, len(grid)):\n",
    "            for j in range(0, len(grid[0])):\n",
    "                if grid[i][j] < 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        return sum(bisect_left(row[::-1], 0) for row in grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count=0\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                if j <0:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        return sum(bisect_left(row[::-1], 0) for row in grid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)   ##row\n",
    "        n = len(grid[0])    ##coloum\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        s = 0\n",
    "        for arr in grid:\n",
    "            pos = -1\n",
    "            while(l<=r):\n",
    "                m = l + (r-l)//2\n",
    "                if 0 <= arr[m]:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    pos = m\n",
    "                    r = m - 1\n",
    "                # print(l, r, m, pos)\n",
    "            if pos != -1:\n",
    "                s += (n-1 - pos + 1) \n",
    "                r = pos\n",
    "            else:\n",
    "                r = n-1\n",
    "            l = 0           \n",
    "            # print(arr, l, r, m, pos, s)\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                if j < 0:\n",
    "                    res += 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        r=len(grid)\n",
    "        c=len(grid[0])\n",
    "        i,j=r-1,0\n",
    "        count=0\n",
    "        while i>=0 and j<=c-1:\n",
    "            if grid[i][j]<0:\n",
    "                count+=(len(grid[0])-j)\n",
    "                i-=1\n",
    "            elif grid[i][j]>=0:\n",
    "                j+=1\n",
    "        return count            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for num in grid:\n",
    "            left, right = 0, len(num) - 1\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if num[mid] >= 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            count += len(num) -left\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] < 0:\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        n = len(grid[0])\n",
    "        col = n - 1 \n",
    "        for i in range(len(grid)):\n",
    "            while col >= 0:\n",
    "                if grid[i][col] >= 0:\n",
    "                    ans += (n - 1 - col)\n",
    "                    break\n",
    "                col -= 1\n",
    "            if col < 0:\n",
    "                ans += n\n",
    "        return ans\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n = len(grid),len(grid[0])\n",
    "\n",
    "        cnt = 0 \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]<0:\n",
    "                    cnt += 1\n",
    "        \n",
    "        return cnt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        for gir in grid:\n",
    "            for j in gir:\n",
    "                if j<0:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        for row in grid:\n",
    "            l,r=0,len(row)-1\n",
    "            while l<=r:\n",
    "                mid=(r-l)//2+l\n",
    "                if row[mid]>=0:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid-1\n",
    "            sum_minus=len(row)-l\n",
    "            ans+=sum_minus\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for row in grid:\n",
    "            for num in row:\n",
    "                if num < 0:\n",
    "                    count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        for i, row in enumerate(grid):\n",
    "            if row[0] < -1:\n",
    "                cnt += len(row) * (len(grid) - i)\n",
    "                break\n",
    "            for j, x in enumerate(row):\n",
    "                if x < 0: cnt += 1\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        sum=0\n",
    "        for i in grid:\n",
    "            for j in i:\n",
    "                if j<0:\n",
    "                    sum+=1\n",
    "        return sum            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        i,j=0,0\n",
    "        count=0\n",
    "        while i<=m-1 :\n",
    "            while j<=n-1:\n",
    "                if grid[i][j]>= 0 :\n",
    "                    j+=1\n",
    "                else :\n",
    "                    count+=(n-j)*(m-i)\n",
    "                    n=j\n",
    "                    break\n",
    "            i+=1\n",
    "            j=0\n",
    "        return count\n",
    "\n",
    "                    \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        count = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            j = 0\n",
    "            while j < n :\n",
    "                if grid[i][j] < 0:\n",
    "                    count += n - j\n",
    "                    break\n",
    "                j += 1\n",
    "        \n",
    "        return count\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)   ##row\n",
    "        n = len(grid[0])    ##coloum\n",
    "        l = 0\n",
    "        r = n - 1\n",
    "        s = 0\n",
    "        for arr in grid:\n",
    "            pos = -1\n",
    "            while(l<=r):\n",
    "                m = l + (r-l)//2\n",
    "                if 0 <= arr[m]:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    pos = m\n",
    "                    r = m - 1\n",
    "                print(l, r, m, pos)\n",
    "            if pos != -1:\n",
    "                s += (n-1 - pos + 1) \n",
    "                r = pos\n",
    "            else:\n",
    "                r = n-1\n",
    "            l = 0           \n",
    "            print(arr, l, r, m, pos, s)\n",
    "            # break\n",
    "        return s\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        res= 0\n",
    "        for lst in grid:res += bisect.bisect_left(lst[::-1], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def countNegatives(self, grid):\n",
    "        \n",
    "        if not grid or not grid[0]:\n",
    "            return 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] < 0:\n",
    "                    res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count=0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j]<0:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        i, j, ans = 0, m-1, 0\n",
    "        while i < n:\n",
    "            while j >= 0 and grid[i][j] < 0:\n",
    "                j -= 1\n",
    "            ans += m - j - 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        m  = len(grid[0])\n",
    "        p = m-1\n",
    "        for i in range(len(grid)):\n",
    "            j = p \n",
    "            while j > -1 :\n",
    "                if grid[i][j] >= 0 :\n",
    "                    p = j \n",
    "                    break \n",
    "                j -= 1\n",
    "            ans += m-j-1 \n",
    "\n",
    "        return ans  \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "#  [ 4,  3,  2,  -1]\n",
    "#  [ 3,  2,  1,  -1]\n",
    "#  [ 1,  1, -1,  -2]\n",
    "#  [-1, -1, -2,  -3]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        res= 0\n",
    "        for lst in grid:res += bisect.bisect_left(lst[::-1], 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                if grid[i][j] < 0:\n",
    "                    count += 1\n",
    "        return count\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count=0\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]<0:\n",
    "                    count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        for g in grid:\n",
    "            idx = bisect.bisect_right(g[::-1], -1)\n",
    "            res += idx \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n = 0\n",
    "        for row in grid:\n",
    "            if row[-1] >= 0:\n",
    "                continue\n",
    "            if row[0] < 0:\n",
    "                n += len(row)\n",
    "                continue\n",
    "            start = 0\n",
    "            end = len(row) - 1\n",
    "            mid = (start + end) >> 1\n",
    "            while start <= end:\n",
    "                if row[mid] >= 0:\n",
    "                    start = mid + 1\n",
    "                else:\n",
    "                    end = mid - 1\n",
    "                mid = (start + end) >> 1\n",
    "            n += len(row[start:]) if row[start] < 0 else len(row[start+1:])\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        def bianrySearch(i, j, nums):\n",
    "            lens = j\n",
    "            while i < j:\n",
    "                mid = (i+j) >> 1\n",
    "                if nums[mid] >= 0: i = mid + 1\n",
    "                else: j = mid \n",
    "            return lens - i + 1 if nums[i] < 0 else 0\n",
    "\n",
    "        n, m  = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            if grid[i][0] < 0:\n",
    "                res += (n-i)*m\n",
    "                break\n",
    "            size = bianrySearch(0, m-1, grid[i])\n",
    "            res += size\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        i, j, ans = 0, m-1, 0\n",
    "        for x in grid:\n",
    "            while j >= 0 and grid[i][j] < 0:\n",
    "                j -= 1\n",
    "            ans += m - j - 1\n",
    "            i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        return sum(bisect_left(row[::-1],0) for row in grid)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countNegatives(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        m = len(grid) # 行\n",
    "        n = len(grid[0])  # 列，每行元素的个数\n",
    "        i, j = m - 1, 0  # 矩阵左下角元素的坐标\n",
    "        while i >= 0 and j <= n - 1:\n",
    "            if grid[i][j] < 0:\n",
    "                count += n - j  # 检索到负数时，该行剩余元素皆为负数\n",
    "                i -= 1  # 上移一行\n",
    "            if grid[i][j] >= 0:\n",
    "                j += 1  # 右移一位\n",
    "        return count\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
